#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* token types */
#define NUM	256
#define EOS	257

/* communication variables */
int token;		/* type */
int attribute;	/* attribute */

/* prototypes */
int 	expr(), term(), factor();
int 	get_token();
void 	match( int );
void 	error( char * );


main()
{
	int value;

	token = get_token();
	value = expr();
	fprintf( stderr, ">>> %d\n", value );
	if ( token != EOS ) {
		error( "extraneous symbols" );
	}
}

/* parser */
/* Expr -> Term Expr'
 * Expr' -> '+' Term Expr' | '-' Term Expr' | empty
 */
int expr()
{
	int value = term();
	while (1) {
		if ( token == '+' ) {
			match('+');
			value += term();
		}
		else if ( token == '-' ) {
			match('-');
			value -= term();
		}
		else return value;
	}
}

/* Term -> Factor Term'
 * Term' -> '*' Term | empty
 */
int term()
{
	int value = factor();
	if ( token == '*' ) {
		match('*');
		value *= term();
	}
	return value;
}

/* Factor -> '(' Expr ')' | NUM
 */
int factor()
{
	int value;
	if ( token == '(' ) {
		match('(');
		value = expr();
		match(')');
		return value;
	}
	else if ( token == NUM ) {
		value = attribute;
		match(NUM);
		return value;
	}
	else {
		error( "factor: illegal token" );
	}
}



/* scanner */
int get_token()
{
	int c, value;

	while (1) {
		switch (c = getchar()) {
		/* operators: treat as own token type */
		case '+': case '-': case '*':
		case '(': case ')':
			fprintf( stderr, "[%c]", c );
			return c;
		/* whitespace ::= [ \t]+	 ignored */
		case ' ': case '\t':
			continue;
		case '\n':
			fprintf( stderr, "\n" );
			return EOS;
		default:
			/* NUM ::= [0-9]+ */
			if ( isdigit(c) ) {
				value = 0;
				do {
					value = value * 10 + c - '0';
				}
				while ( isdigit(c = getchar()) );
				ungetc( c, stdin );
				attribute = value;
				fprintf( stderr, "[NUM:%d]", attribute );
				return NUM;
			}
			else if ( c == EOF ) {
				return EOS;
			}
			else {
				fprintf( stderr, "{%c}", c );
				error( "illegal token" );
			}
		}
	}
}

/* helpers */

void match( int expected_token )
{
	if ( token == expected_token ) {
		token = get_token();
	}
	else {
		error( "unexpected token" );
	}
}

void error( char *message )
{
	fprintf( stderr, "Error: %s\n", message );
	exit(1);
}
















